最短経路決定のタイブレイク

专利摘要:
等価最短（最低コスト）経路の間の一貫性のあるタイブレイク決定は、複数のエンド・ツー・エンド経路のそれぞれに対して順序付けられたノード識別子のセットを比較することにより達成される。或いは、ツリーの分岐するブランチのノード識別子を用いて等価経路の選択が行われることにより、最短経路ツリーが構成されるので、オンザフライで同一の結果が達成されうる。２つの変形は、ネットワーク内のどこで最短経路が計算されるかに拘わらず、等価経路の一貫した選択を可能にする。これは、任意の２個のノード間のトラフィック・フローが、順方向及び逆方向の両方向で、ネットワークを通じて常に同一経路に従うことを保証する。
公开号:JP2011508555A
申请号:JP2010540188
申请日:2008-12-11
公开日:2011-03-10
发明作者:スミス，ピーター アッシュウッド；アラン，デイヴィッド；チアバウト，ジェローム；ブラグ，ナイジェル
申请人:ノーテル・ネットワークス・リミテッド；
IPC主号:H04L12-56

专利说明:

[0001] 本発明は、イーサネット・ネットワークのようなパケット転送通信ネットワークにおける等価最短経路のような複数の候補の中からの経路の一貫性のある選択に関する。]
背景技術

[0002] パケット転送通信ネットワークでは、ノードは、ネットワークのトポロジについて学習し、該トポロジから得た知識に基づきトラフィックを各他のネットワーク・ノードへどのようにルーティングするかを決定しうる。経路選択の主な根拠は経路コストである。経路コストは、ノード間のホップ数の観点から又はノード同士を接続するリンクの帯域幅のような特定の他のメトリック、又はこれらの両方により特定されうる。ＯＳＰＦ（Open Shortest Path First）及びＩＳ−ＩＳ（Intermediate System-to-intermediate System）は、広く用いられているリンク状態プロトコルであり、各ノードの経路コストの広告（アドバタイズメント）に基づき最短経路を確立する。これらのプロトコルは、通常、複数の等価経路の間のタイブレイクを試みない。代わりに、これらのプロトコルは、通常、幾つかの等価経路に跨ってトラフィックを展開する。展開のアルゴリズムは、特定されず、ルータ毎に変わりうる。或いは、展開のアルゴリズムは、単一経路の局所的な選択を行うが、他のルータにより行われた選択との一貫性を考慮しない。従って、何れの場合にも、逆方向のフローが順方向で用いられた経路を用いると保証されない。]
[0003] ＭＯＳＰＦ（Multicast Open Shortest Path First）のようなマルチキャスト・ルーティング・プロトコルは、同一の最短経路ツリーを構成するネットワーク内の各ルータに依存する。このため、ＭＯＳＰＦは、リンクの種類、ＬＡＮ対ポイント・ツー・ポイント、及びルータ識別子に基づくタイブレイク・スキームを実装し、同一のツリーが生成されることを保証する。しかしながら、最大識別子を有する親にタイブレイクの決定の基礎を置くことは、概して、逆方向フローに用いられる経路が順方向フローに用いられた経路と同一でないことを暗示する。]
[0004] スパニング・ツリー・プロトコル（Spanning Tree Protocol：ＳＴＰ、Rapid Spanning Tree Protocol：ＲＳＴＰ、Multiple Spanning Tree Protocol：ＭＳＴＰ）は、任意のトポロジにおいてループのないスパニング・ツリーを作成する方法である。スパニング・ツリー・プロトコルは、ネットワーク内の各ノードにより実行される。全てのスパニング・ツリー・プロトコルは、（ブリッジ識別子、ポート識別子に基づき）局所的なタイブレイク決定を用い、等価経路間で選択を行う。スパニング・ツリーでは、最初にルート・ノードが選ばれ、次に全てのノードにより該ルートに関するツリーが構成される。従って、行き及び戻りのトラフィックについて全ての経路は対称であるが（本質的に、単純なツリーはこれを唯一の可能な構成とする）、選択処理は遅く、単純なツリー構造は如何なる冗長な容量も用いることができない。同様に、Radia Perlmanの提案するRbridgeは、親ノードの識別子をタイブレイカとして用いる。]
[0005] Mick Seamanは、最短経路ブリッジをＩＥＥＥ８０２．１ワーキング・グループに提案し（http://www.ieee８０２.org/l/files/public/docs２００５/new-seaman-shortest-path-０３０５-０２.pdf）、「カット・ベクトル」を追加することにより一貫したタイブレイク決定を実行する、ＲＳＴＰ（Rapid Spanning Tree Protocol）の簡易なプロトコル拡張について記載している。この提案は、ノード毎のＶＩＤを用い、ノード毎にスパニング・ツリーを識別する。ブリッジにより送信される必要のある全ての情報を単一の適法なイーサネット・フレームに適合させるために、この技術は、現在の所、イーサネット・ネットワークの大きさを３２個のブリッジに制限している。]
[0006] 図１は、平凡なネットワークの例でさえ親ノードの識別子に基づくタイブレイク方法が対照的な経路の生成にどのように障害するかを示す。本例では、リンクは等しいコストを有すると考えられ、従って経路コストの決定は単にホップ数を考慮する。最初に、ＡからＢへの経路の計算を検討する。計算がノード２に達するとき、等価経路の存在が発見される。第１の経路（Ａ−１−３−６）及び第２の経路（Ａ−１−４−５）がある。タイブレイク・アルゴリズムは、最小識別子を有する親ノードに基づき経路を選択する場合、第２の経路（Ａ−１−４−５）を選択するだろう。何故なら、ノード識別子５はノード識別子６よりも小さいからである。次に、ＢからＡへの経路の計算を検討する。計算がノード１に達するとき、等価経路の存在が発見される。第１の経路（Ｂ−２−６−３）及び第２の経路（Ｂ−２−５−４）がある。同一のタイブレイク基準を用いると、タイブレイク・アルゴリズムは、第１の経路（Ｂ−２−６−３）を選択する。何故なら、ノード識別子３はノード識別子４よりも小さいからである。従って、ノードＡ及びＢにより行われる最短経路計算は一貫性のない結果をもたらすことが分かる。] 図１
発明が解決しようとする課題

[0007] ＩＥＥＥ８０２．１ａｑに提案されたＰＬＳＢ（Provider Link State Bridging）のような幾つかの新興のプロトコルには、ユニキャスト及び未知の／マルチキャスト・トラフィックの両方に対してネットワーク全体で一致した転送を維持し、及び順方向及び逆方向のフローの両方で共通経路を用いるという要件がある。従って、等価経路の間でタイブレイクが起こるとき、複数のノードが一貫して同一の決定に到達できることが重要である。更に、ノードは最小量の処理能力でタイブレイクを実行できることが望ましい。]
課題を解決するための手段

[0008] 本発明の第１の態様は、パケット転送ネットワークの第１のノードでパケットを転送するときに用いる転送情報を決定する方法を提供する。当該方法は：前記第１のノードと前記ネットワークの第２のノードとの間の最短経路を決定し、複数の最短経路が実質的に等価であるときを決定する。方法は、実質的に等価な経路毎に、該経路内にあるノードのセットを定めるノード識別子のセットを形成するし、該第１の順序付け基準を用いてノード識別子の各セットを順序付け、経路識別子を形成する。第１の順序付け基準はノード識別子が前記経路内に現れる順序とは独立である。方法は、前記経路識別子を比較することにより、複数の等価経路の間で選択する。ネットワークの各ノードはユニークなノード識別子を有する。]
[0009] 有利なことに、第１の順序付け基準は昇順の辞書式順序又は降順の辞書式順序であるが、全体的に順序付けられたノード識別子のセットを生成する如何なる順序付け基準も用いられうる。]
[0010] 望ましくは、方法は、第２の順序付け基準を用いて、複数の経路識別子を順序付きリストに順序付ける段階；を更に有する。同様に、第２の順序付け基準は昇順の辞書式順序、降順の辞書式順序、又は全体的に順序付けられた経路識別子のセットを生成する如何なる順序付け基準であってもよい。]
[0011] 本発明の別の態様は、パケット転送ネットワークの第１のノードでパケットを転送するときに用いる転送情報を決定する方法を提供する。方法は、最短経路ツリーを繰り返し形成することにより、前記第１のノードと前記ネットワークの第２のノードとの間の最短経路を決定する段階；前記最短経路ツリーを形成する間、複数の経路が等価であるときを決定する段階；を有する。各等価経路は、複数の等価経路に共通の分岐ノードから分岐するブランチを有する。方法は、各分岐するブランチで、第１の選択基準を用いてノード識別子を識別し、ブランチ識別子を形成し、前記ブランチ識別子を比較することにより、複数のブランチの間で選択する。]
[0012] 有利なことに、方法は、辞書式順序のような全体的な順序付け基準を用い、各ブランチのノード識別子を比較し選択する。]
[0013] 有利なことに、方法は、前記分岐ノードへ引き返す間に、前記各分岐ブランチ内の第１の選択基準を満たすノード識別子を記録する。これは、計算を更に簡単にし、記憶要件を低減するので有利である。]
[0014] 本発明の２つの態様は、異なる第１の順序付け／選択基準及び共通の第２の順序付け／選択基準を用いること、又は共通の第１の順序付け／選択基準及び異なる第２の選順序付け／択基準を用いることにより２つの等価経路を選択するために用いられてよい。３又は４個の等価経路は、第１及び第２の順序付け／選択基準を複数のノードで一貫して適用し、順序付きリスト内の特定の位置で識別子を選択することにより、同様の方法で選択されてよい。]
[0015] 本発明は、タイブレイカとして用いられ、複数のエンド・ツー・エンド経路のそれぞれに対して順序付けられたノード識別子のセットを比較することにより、等価経路間で選択する。或いは、選択の決定が行われる必要のある場所で局所的に、ツリーの分岐するブランチのノード識別子を用いて等価経路の選択が行われることにより、最短経路ツリーが構成されるので、オンザフライで同一の結果が達成されうることが分かっている。これは、計算量を低減し、格納される必要のあるデータ量を低減するので有利である。ブランチは対に基づき比較され、計算量を更に低減する。これは、ネットワークの規模及び複雑性が増大するとき、特に重要である。本発明の２つの変形は、ネットワーク内のどこで最短経路が計算されるかに拘わらず、等価経路の一貫した選択を可能にするという重要な特性を有する。これは、任意の２個のノード間のトラフィック・フローが、順方向及び逆方向の両方向で、ネットワークを通じて常に同一経路に従うことを保証する。]
[0016] 本発明は、最短経路を決定する如何なる特定の方法にも限定されるものではない。ダイクストラのアルゴリズム、フロイドのアルゴリズム、又は如何なる他の適切な代替が用いられてもよい。]
[0017] 本発明は、正確に同一の値を有する等価経路間、又はリンク・メトリック又はホップ数の観点から互いに所望のオフセットの範囲内にある経路間のタイブレイカとして用いられてよい。これは、現実世界では、適確な経路のセット間で多様性を増すので望ましい。例えば、一般的に、任意の２つの終端点の間で正確に等価であることを義務づけて、対照的にノード及びリンクを展開することは常にコスト効率が良いとは限らない。異なる経路のホップ数が互いに１ホップの範囲内にある必要があることまで制約を緩和することにより、適度な非対称が依然として適確な経路を生じ、及びループ経路を達成するためには最低限２ホップの差が必要なので、ループのないトポロジが依然として保証されうる。]
[0018] 理解されるべき点は、用語「最短経路」が距離のみに基づく経路の決定に限定されないこと、リンクの「コスト」を特定するために用いられうる如何なるメトリック又はメトリックの組み合わせも包含することである。メトリックの非網羅的リストは、距離、ホップ数、容量、速度、使用量、可用性である。]
[0019] 方法は、等価最短経路の選択が、障害ノード又はリンクのような選択された経路上にあるネットワークの部分の除去により影響を受けないという点で安定している。]
[0020] 有利なことに、ネットワークはイーサネット・ネットワークであるが、本発明は特に対照的なトラフィック・ルーティング経路という要件を有するような他の種類のパケット転送ネットワークにも適用可能である。]
[0021] 本願明細書に記載された機能は、ソフトウェア、ハードウェア、又はそれらの組み合わせで実施されてもよい。本発明は、適切なプログラムされたコンピュータ又は如何なる形式の処理装置によって実施されてもよい。従って、本発明の別の態様は、上述の何れかの方法を実施するソフトウェアを提供する。ソフトウェアは、電子記憶装置、ハード・ディスク、光ディスク又は他の機械可読記憶媒体に格納されてもよい。ソフトウェアは、機械可読記憶媒体に格納されたコンピュータ・プログラムとして分配されてもよく、又はネットワーク接続を介してノードにダウンロードされてもよい。]
[0022] 本発明の更なる態様は、上述の任意の方法を実行するようにされるプロセッサを有するネットワーク・ノードを提供する。]
[0023] 本発明の更なる態様は、それぞれ上述の方法を一貫して適用し等価経路の間で選択するノードのネットワークを提供する。]
図面の簡単な説明

[0024] 本発明の実施形態は、例として以下の図を参照し詳細に説明される。
等価経路を有するネットワーク・トポロジを示す。
本発明が実施されうるパケット転送ネットワークの例を示す。
図２のブリッジ・ノードの１つの装置の概略を示す。
タイブレイク決定の局所性を示す。
最短経路の計算を説明する例であるネットワーク・トポロジを示す。
最短経路の計算を説明する例であるネットワーク・トポロジを示す。
最短経路の計算を説明する例であるネットワーク・トポロジを示す。
最短経路の計算を説明する更なる例であるネットワーク・トポロジを示す。
図８に示したネットワーク・トポロジの最短経路計算のタイブレイクを行う段階を示す。
図８に示したネットワーク・トポロジの最短経路計算のタイブレイクを行う段階を示す。
図８に示したネットワーク・トポロジの最短経路計算のタイブレイクを行う段階を示す。
メッシュ型ネットワークに二重に収容されたノードの例を示す。
本発明のタイブレイク方法の特性を説明する。
本発明のタイブレイク方法の特性を説明する。] 図２ 図８
実施例

[0025] 図２は、本発明が実施されうるリンク状態プロトコルにより制御されるイーサネット・ネットワーク１０の例を示す。図３は、ノード４１−４８のうちの１つの装置の概略を示す。メッシュ型ネットワークを形成するノード（ブリッジ又はブリッジ・ノードとも称される）４１−４８は、リンク状態広告５６を互いに交換する。これは、良く理解されているリンク状態ルーティング・システムの仕組みにより達成される。ルーティング・システム・モジュール５１は、リンク状態転送プロトコルを用いて、ネットワーク・トポロジに関する情報５６をネットワーク内のピア・ノードと交換する。この情報交換により、ノードは、ネットワーク・トポロジの同期された展望図を生成できる。各ノードで、最短経路決定モジュール５２は、各他のノードへの最短経路を決定する最短経路ツリーを計算する。モジュール５２により決定された最短経路は、ネットワークを通じてトラフィックを方向付けるために、転送情報ベース（Forwarding Information Base：ＦＩＢ）にエントリを投入するために用いられる。以下に更に詳細に記載されるように、モジュール５２が複数の等価経路に層遇するとき、状況が生じる。タイブレイク・モジュール５３は、一貫性のある方法で等価経路のうちの１つ（又は複数）を選択する。通常動作では、パケットはノードで受信され５７、宛先検索モジュール５５はＦＩＢ５４を用いて受信したパケットが転送５８されるべきポート（又はマルチキャスト配信の場合には複数のポート）を決定する。ＦＩＢ５４内に有効なエントリがない場合、パケットは廃棄されてもよい。理解されるべき点は、図３に示されるモジュールが単に説明を目的としており、当業者により理解されるようにノードの複数のモジュール間の機能を結合又は分散することにより実施されてもよいことである。] 図２ 図３
[0026] 種々の最短経路アルゴリズムが、所与のノードが所与のブリッジ対の間の最短経路上にあるかどうかを決定するために用いられてもよい。ノード対の間の最短経路を計算するために、Floydのアルゴリズム（R.Floyd：Algorithm ９７（最短経路）、Communications of theACM、７:３４５、１９６２）又はDijkstraの単一始点最短経路アルゴリズム（E.W.Dijkstra：A note on two problems in connexion with graphs、Numerical Mathematics、１:２６９-２７１、１９５９）のような全ての対の最短経路アルゴリズムがノード４１−４８内で実施されてもよい。]
[0027] 理解されるべき点は、如何なる適切な最短経路アルゴリズムも利用されてよいことである。最短経路アルゴリズムにより用いられるリンク・メトリックは、トラフィック工学情報を考慮するために静的又は動的に変更されてもよい。例えば、リンク・メトリックは、容量、速度、使用量及び可用性のようなコストの指標を有してもよい。]
[0028] 課題の前置きとして、先ず、等価経路の間の一貫性のある決定を行いうるタイブレイク・アルゴリズムの要件を説明する。以下の表１に要件の一覧を示す。]
[0029] タイブレイク・アルゴリズムの真髄は、常に「動作する」ことである。アルゴリズムは、どの経路セットを提示されるかに拘わらず、常に１つの且つ唯一の経路を選択できなければならない。従って、最初に最も重要なことは、タイブレイク・アルゴリズムが完成されたものであることである（１）。]
[0030] 一貫性のあるタイブレイクのために、アルゴリズムは、等価経路が発見されタイブレイクが実行される順序に拘わらず、同一の結果を生成しなければならない。つまり、タイブレイク・アルゴリズムは、交換可能であり（２）及び連想可能（associative）（３）でなければならない。経路対が考慮される順序に拘わらず、３個の経路の間のタイブレイクが同一の結果を生成しなければならないという要件（３）は、明白ではないが、等価経路がネットワークを通じた計算方向に依存して異なる順序で発見されるときに一貫性のある結果のために不可欠である。タイブレイク・アルゴリズムは対称でなければならない（４）。つまり、タイブレイク・アルゴリズムは、経路の方向に拘わらず同一の結果を生成しなければならない。２個のノードＡ及びＢの間の最短経路は、ＢとＡとの間の最短経路の逆でなければならない。最後に、局所性は、ルーティング・システムにより利用される最短経路の非常に重要な特性である（５）。局所性の特性は、単に、最短経路のサブ経路も最短経路であることを意味する。最短経路のこの一見して些細な特性は、宛先に基づく転送を用いるパケット・ネットワークで重要な用途を有する。これらのネットワークでは、経路に沿った中間ノードにおける転送決定は、パケットの送信元アドレスではなく、単にパケットの宛先アドレスに基づく。従って、ノードの転送情報を生成するために、ノードは、単に自身から全ての他のノードへの最短経路を計算するだけでよく、生成された転送情報の量は、ネットワーク内のノード数に関して、二次関数的にではなく線形的に増大する。従って、宛先に基づく転送を可能にするために、タイブレイク・アルゴリズムは、最短経路の局所的特性を維持しなければならない。タイブレイク・アルゴリズムにより選択された最短経路のサブ経路は、タイブレイク・アルゴリズムにより選択された最短経路でなければならない。]
[0031] 計算効率の検討は、別の一見したところ異なる要件をタイブレイク・アルゴリズムに課す。アルゴリズムは、等価経路が発見されると直ぐにタイブレイクの決定を行えるべきである。図４は、この点を図示する。中間ノードＩは、２つの等価経路ｐ及びqによりノードＡに、及び別の等価経路の対ｒ及びｓによりノードＢに接続される。従って、ノードＡ及びＢの間に４個の等価経路ｐ＋ｒ、ｐ＋ｓ、ｑ＋ｒ、ｑ＋ｓがあり、全ての経路がノードＩを通過する。ＡからＢまでの最短経路の計算が進むと、ノードＡとＩとの間の等価サブ経路の存在が先ず発見されるだろう。これらの２個の経路の知識を繰り返す必要を回避するために、タイブレイク・アルゴリズムは、第２の等価最短サブ経路が発見されると直ぐに、これらの経路の間で選択可能であるべきである。中間ノードで行われたタイブレイクの決定は、計算の結果に最終的に影響を及ぼす。ノードＡ及びＩの間の２個のサブ経路ｐ及びｑのうちの１個を削除することにより、アルゴリズムは、ノードＡ及びＢの間の４個の最短経路のうちの２個を更なる検討から除外する。同様に、逆方向では、タイブレイク・アルゴリズムは、最終決定を行う前にサブ経路ｒ及びｓの間で選択する。これらの局所的決定は、互いに一貫していなければならない。特に、経路が同様に延長されるべきである場合には、２個の等価経路間の選択は同一であるべきである。例えば、図３に示された場合には、タイブレイク・アルゴリズムは、次の４個の同一性を検証すべきである。
tiebreak(concat(p,r),concat(q,r))=concat(tiebreak(p,q),r)、
tiebreak(concat(p,s),concat(q,s))=concat(tiebreak(p,q),s)、
concat(p,tiebreak(r,s))=tiebreak(concat(p,r),concat(p,s))、
concat(q,tiebreak(r,s))=tiebreak(concat(q,r),concat(q,s))
対称性（４）及び局所性（５）の条件は、タイブレイク・アルゴリズムが一貫した局所的決定を行うこと、等価最短経路が存在する場合に単一始点最短経路アルゴリズムの非常に効率的実施を実現するために利用され得るという事実、を保証するために、共に必要十分であることが分かる。] 図３ 図４
[0032] 表１に示された要件の一覧は網羅的であることを目的としていないので、表１に含まれうる他の最短経路の特性も存在する。例えば、最短経路の一部でないリンクがグラフから除去される場合、最短経路は影響を受けない。同様に、タイブレイク・アルゴリズムの複数の等価経路間の選択は、選択された経路の一部でないリンクがグラフから除去された場合に、及び該リンクがアルゴリズムにより拒否された幾つかの等価経路の一部である場合でも、影響を受けるべきではない。]
[0033] 一貫性のあるタイブレイク・アルゴリズムの第１の実施形態を以下に説明する。本アルゴリズムは、経路毎に経路識別子を形成することにより開始する。経路識別子は、ネットワークを通る経路により通過される各ノードの識別子の順序付きリストである。ノード識別子は、辞書式順序でソートされる。経路識別子は、結果として生じる順序付きノード識別子の連結である。図５は、終端ノードＡ、Ｂ及び中間ノード０−９を有する例であるネットワークを示す。ノードＡ及びＢの間の（図５の上側に沿った）第１の経路は、ノード識別子Ａ−０−５−６−１−４−８−Ｂを有するノードを通過する。ノード識別子のリストを昇順の辞書式順序で順序付けた後、経路は経路識別子０１４５６８ＡＢにより表すことができる。この構成は、経路及びその逆が同一の経路識別子を有することを保証する。更に、アルゴリズムは最短経路のみ又はほぼ最短経路のみを扱うので、２個の経路−直接経路及び対応する逆経路−は１個の識別子を共有しうる。最後に、タイブレイク・アルゴリズムは、最小（又は最大）経路識別子を有する経路を単に選択する。アルゴリズムは次のように要約できる。
（１）第１の順序付け基準に従い、経路内のノードの識別子のセットをソートする。これは、ノード識別子のセットの全体の順序付けを達成する。好適な第１の順序付け基準は、昇順又は降順の辞書式順序である。
（２）順序付けられたノード識別子のセットを連結し、経路識別子を生成する。
（３）第２の順序付け基準に従い、経路識別子のセットをソートする。これは、経路識別子のセットの全体の順序付けを達成する。好適な第２の順序付け基準は、昇順又は降順の辞書式順序である。
（４）経路識別子がソートされた経路識別子のセットの一端（最初又は最後）に現れる経路を選択する。有利なことに、この段階は、順序付けられた経路識別子のセット内の最初に現れる経路識別子を選択する。] 図５
[0034] 本アルゴリズムを実行するネットワーク内の各ノードは、同一の経路を選択するために、一貫して同一の順序付け基準を使用し、経路識別子のセット内の同一の合意のとれた位置にある経路を選択する。]
[0035] 用語「辞書式順序」は、ノード識別子のセットが識別子の大きさの順に整列されることを意味する。従って、ノード識別子がアルファベットである場合は、ノード識別子のセットはアルファベット順、Ａ、Ｂ、Ｃ、Ｄ、．．．等に整列され、ノード識別子が数字である場合は、ノード識別子のセットは番号順に整列される。明らかに、本方式は、如何なる方法でラベル付けされたノード、及び識別子の種類の如何なる組み合わせにも適合する。例えば、数字と文字の混合は、文字に対する数字の順序（例えば、最初に数字を次に文字を順序付ける）を合意することにより順序付けできる。或いは、各文字は、該文字の情報交換用米国標準コード（American Standard Code for Information Interchange：ＡＳＣＩＩ）で与えられてよく、及びＡＳＣＩＩコードは昇順（又は降順）にソートされてよい。各ノードは、同一の約束事を使用して、同一の方法で経路のノード識別子を順序付ける。（厳密には経路とその逆経路とを有する対の間の）経路と該経路の識別子との間に１対１マッピングが存在し、経路識別子の全体の順序付けが存在するので、本アルゴリズムは一貫した結果を生成する。]
[0036] 図５に戻ると、順序付けの後、ノードＡ及びＢの間の上側の経路は経路識別子０１４５６８ＡＢにより表される。同様に、ノードＡ及びＢの間の第２の経路はノードＡ−０−７−９−１−４−８−Ｂを通過し、順序付けの後、経路識別子０１４７８９ＡＢにより表すことができる。最後に、ノードＡ及びＢの間の（図５の下側に沿った）第３の経路はノードＡ−０−７−９−２−３−８−Ｂを通過し、順序付けの後、経路識別子０２３７８９ＡＢにより表すことができる。タイブレイク・アルゴリズムは、順序付けされた経路識別子の各要素を合意した方向で比較する。本例では、使用される約束事は、経路識別子が特定の方向に（例えば左から右へ）比較されるとき、各ノードが順序付けされた経路識別子のうち最も低いものを選択することである。３個の等価経路の場合に、順序付けされた経路識別子は次の通りである。
０１４５６８ＡＢ
０１４７８９ＡＢ
０２３７８９ＡＢ
識別子の左側の要素から開始すると、全ての３個の経路識別子は「０」で始まる。次の要素は「１」又は「２」なので、上２個の識別子だけが更に検討を必要とする。４番目の要素に到達すると、「０１４５．．．」は「０１４７．．．」よりも小さいので、一番上の経路が選択される。ＩＳ−ＩＳ及びイーサネット（登録商標）における実際のノード識別子は、６個の８ビットのバイトを有し、通常は００−ｅ０−７ｂ−ｃ１−ａ８−ｃ２のような１６進数の文字列で表記される。一貫して使用される場合、ノードのニックネームが用いられてもよい。] 図５
[0037] 図６は、別の順序付け基準の効果を示す単純なネットワーク・トポロジを示す。２個のノードＸ、Ｙは、ノード識別子１−８を有する４個の等価経路により接続される。以下に４個の可能な選択肢を説明する。] 図６
[0038] −ノードＩＤを昇順によりソートし、経路ＩＤを昇順によりソートし、最初の（最も小さい）経路ＩＤを選択する。各経路内のノード識別子が大きさの昇順で順序付けされる場合（例えば、ノード１、７を有する一番上の経路は１７になる）、経路識別子１７、２８、３５、４６を得る。これらの経路識別子を大きさの昇順で整列し、順序付きリスト内の最初の経路識別子を選択すると、ノード１及び７を有する最初の（一番上の）経路を選択する結果となる。]
[0039] −ノードＩＤを昇順によりソートし、経路ＩＤを昇順によりソートし、最後の（最も大きい）経路ＩＤを選択する。この選択肢は、ノード４及び６を有する最後の（一番下の）経路を選択する結果となる。]
[0040] −ノードＩＤを降順によりソートし、経路ＩＤを昇順によりソートし、最初の（最も小さい）経路ＩＤを選択する。各経路内のノード識別子を大きさの降順でソートすると、経路識別子（７１、８２、５３、６４）を得る。これらの経路識別子を大きさの昇順で整列し（５３、６４、７１、８２）、順序付きリスト内の最初の（最も小さい）経路識別子を選択すると、ノード３及び５を有する３番目の経路を選択する結果となる。]
[0041] −ノードＩＤを降順によりソートし、経路ＩＤを昇順によりソートし、最後の（最も大きい）経路ＩＤを選択する。この選択肢は、ノード８及び２を有する２番目の経路を選択する結果となる。]
[0042] 以下に更に詳細に記載されるように、ノードが複数の異なる順序付け及び／又は選択基準を適用して複数の等価経路を選択することが望ましい状況がある。]
[0043] これまでは本願明細書は、アルゴリズムが局所的でないこと、タイブレイクが全ての等価経路が見付かった後に実行されることを想定していた。しかしながら、枝分かれするブランチにあるノードのみを考慮することにより、本アルゴリズムの局所的バージョンが同一の結果を生成しうることが分かっている。実際に、タイブレイクの結果は、枝分かれするブランチ内の最小ノード識別子の相対的位置にのみ依存する。一貫性のあるタイブレイク・アルゴリズムの第２の実施形態は次のように要約できる。
（１）第１の選択基準を満たす第１の経路の枝分かれするブランチ内のノード識別子を見付ける。これは、第１の経路のブランチ識別子とみなされる。
（２）第１の選択基準を満たす第２の経路の枝分かれするブランチ内のノード識別子を見付ける。これは、第２の経路のブランチ識別子とみなされる。
（３）第２の選択基準を用いて複数の経路の内の１つを選択する。これは、段階（１）及び（２）により選択されたブランチ識別子に対して行われる。]
[0044] 第１の選択基準の好適な選択肢は、辞書式順序（昇順又は降順の辞書式順序）のような全体の順序付け方式を用いてノード識別子が整列されるとき、最初の（又は最後の）ノード識別子を見付けることである。以下に説明されるように、本方式がブランチ内のノード識別子のセット全体に適合して該セットを順序付ける必要はない。実際に、本方式は、辞書式順序を意識してノード識別子の対を繰り返し比較できる。同様に、第２の選択基準の好適な選択肢は、辞書式順序（昇順又は降順の辞書式順序）のような全体の順序付け方式を用いてブランチ識別子が整列されるとき、最初の（又は最後の）ブランチ識別子を見付けることである。]
[0045] 図６を再び参照すると、ノードＸ及びＹの間の４個の等価経路は、親ノードＸから枝分かれする４個の等価なブランチを表しうる。タイブレイク・アルゴリズムは、４個のブランチのうちの１つを選択する必要がある。次の４個の可能な選択肢がある。] 図６
[0046] −各ブランチの最小ノードＩＤを識別する。この結果はブランチ識別子として（１、２、３、４）である。次に、ブランチ識別子のうち最小のものを識別する。これは、ノード１及び７を有する最初の（一番上の）経路を選択する結果となる。]
[0047] −各ブランチの最小ノードＩＤを識別する。次に、ブランチ識別子のうち最大のものを識別する。この選択肢は、ノード４及び６を有する最後の（一番下の）経路を選択する結果となる。]
[0048] −各ブランチの最大ノードＩＤを識別する。この結果はブランチ識別子として（５、６、７、８）である。次に、ブランチ識別子のうち最小のものを識別する。これは、ノード３及び５を有する経路を選択する結果となる。]
[0049] −各ブランチの最大ノードＩＤを識別する。次に、ブランチ識別子のうち最大のものを識別する。この選択肢は、ノード２及び８を有する経路を選択する結果となる。]
[0050] 以下に更に詳細に記載されるように、ノードが複数の異なる順序付け及び／又は選択基準を適用して複数の等価経路を選択することが望ましい状況がある。]
[0051] 本アルゴリズムは非常に簡単に且つ簡単な比較で効率的に実施することができる。図７は、別のネットワーク・トポロジを示す。方法の局所的バージョンは、ノード１３で開始し、ノード１５から通じる２つの枝分かれするブランチの発見へと進む。方法は、２個の別個の経路をノード１６の所まで探索する。ノード１６で２個の経路は再び合流する。この点で、方法は、２個のブランチのそれぞれについてノード識別子を調べる。第１のブランチではノード識別子は１０、１４、１７、２１であり、第２のブランチではノード識別子は１１、１２、１９、２０である。最も低い識別子（１０）を有するブランチは上側の経路の一部である。方法は、ノード１６からノード１５へ向かって単純に同じ道を引き返し、各ブランチで見付かった最小ノード識別子を追跡する。各逆行段階で、方法は、それまでに見付かった最小ノード識別子を、該段階で遭遇した新たなノード識別子と比較する。最小ノード識別子は格納される。方法がノード１５まで同じ道を引き返すとき、２個の最低値（上側のブランチの１０、下側のブランチの１１）は、最小ノード識別子を有するブランチを見付けるために、単純に互いに比較される。これにより、上側の経路の一部を形成する上側のブランチが選択される。このタイブレイクを実行するとき、枝分かれするブランチの両方に共通の経路の一部は、無視される。ネットワーク内の最短経路を発見する最も一般的なアルゴリズムの１つは、ダイクストラ（Dijkstra）のアルゴリズムである（Dijkstra５９）。] 図７
[0052] このアルゴリズムは、経路長が正のホップ・バイ・ホップのリンク・コストの和として定められるとき、グラフ内の一点（始点又はルート・ノード）から全ての可能な終点への最短経路を見付ける問題を解決する。この問題は、屡々、単一始点最短経路問題と称される。グラフではG=(Ｎ，Ｌ)であり、ここでＮはノードのセットであり、Ｌは該ノードを接続するリンクのセットである。ダイクストラのアルゴリズムは、一般にＴＥＮＴと称される優先待ち行列を用い、始点ノードからの距離の昇順でノードを訪ねる。ダイクストラのアルゴリズムを実施するために必要な他のデータ構造を以下に示す。
距離：始点ノードから各ノードへの最短距離の最良推定の配列である。
親：各ノードの先行ノードの配列である。]
[0053] 以下の記載は、知られているダイクストラのアルゴリズムを説明し、複数の等価経路が発見されたときにタイブレイクを実行するためにどのように変更されうるかを説明する。ダイクストラのアルゴリズムは、最も一般的に用いられている最短経路発見アルゴリズムの１つなのでここで説明される。しかしながら、他のアルゴリズムが同様に用いられうることが理解されるだろう。]
[0054] 初期化段階は、始点ノード自体を除いて、各ノードの距離を無限大に設定する。始点ノードはツリーのルートなので、始点ノードの距離はゼロに設定され、始点ノードの親はヌルに設定される。計算の開始時に、優先待ち行列は始点ノードのみを有する。アルゴリズムが進行すると、始点ノードからノードへの経路が見付かったとき、該ノードは優先待ち行列に追加される。ノードと始点ノードとの間の最短経路が見付かった後に、該ノードは、始点ノードからの距離の昇順で優先待ち行列から取り出される。始点ノードから到達可能な全てのノードが優先待ち行列を通して循環されたとき、アルゴリズムは終了する。優先待ち行列ＴＥＮＴが空でないとき、アルゴリズムは以下の段階を実行する。]
[0055] （１）ＴＥＮＴ内の、始点ノードに最も近いノードを見付け、除去する。]
[0056] （２）Ｎに接続される各ノードについて、ノードの始点ノードまでの距離がＮを該ノードの親にすることにより短縮されうる場合には、ノードの親をＮに変更し、ノードの距離を新たな距離に設定し、そしてＴＥＮＴにノードを追加する。アルゴリズムが完了すると、距離（ノード）は、始点ノードからノードまでの最短距離（又はノードが始点ノードから到達可能でない場合には無限大）を有し、親（ノード）は、スパニング・ツリー内の該ノードに先行するノードを有する（始点ノード及び始点ノードから到達可能でないノードを除く）。親の変更がノードの距離を実際に短縮する場合のみ、ノードの親は更新される。これは、複数の等価最短経路が始点ノードと特定の他のノードとの間に存在する場合に、アルゴリズムの実行注に最初に遭遇したもののみが検討されることを意味する。]
[0057] 上述の段階は、ダイクストラのアルゴリズムの従来の段階である。この点で、ダイクストラは一貫性のあるタイブレイク段階を追加するよう変更される。上述の段階２は、次のように変更される。]
[0058] （２）ノードＮに接続される各ノードについて、以下を行う。]
[0059] （２ａ）始点までのノードの距離がＮを該ノードの親にすることにより短縮されうる場合には、ノードの親をＮに変更し、ノードの距離を新たな距離に設定し、そしてＴＥＮＴに該ノードを追加する。]
[0060] （２ｂ）ノードの始点ノードまでの距離がＮを該ノードの親にした後も同一のままである場合には、タイブレイク・アルゴリズムを呼び出し、ノードの親が変更されるべきかどうかを決定する。]
[0061] タイブレイク・アルゴリズムは、２つの枝分かれするブランチの合流点に到達したときに呼び出される。例えば、図７に示されるトポロジを検討すると、ダイクストラのアルゴリズムがノード１３から開始した場合、ノード１５から通じる枝分かれするブランチ（ノード１０、１４、１７、２１を有する上側のブランチ及びノード１１、１２、１９、２０を有する下側のブランチ）が発見され、これらの枝分かれするブランチはノード１６で合流する。] 図７
[0062] ノード１６で、２つのブランチ間で選択するためにタイブレイク・アルゴリズムが呼び出される。]
[0063] 以下の擬似コードは、ＴＥＮＴセットの優先待ち行列の実施を用いて、一貫性のあるタイブレイクを有する変更されたダイクストラのアルゴリズムの実施を示す。エンキュー（Enqueue）処理は２個の引数、待ち行列（キュー）とノードを取り、ノードの始点ノードからの距離に従い、該ノードを待ち行列の正しい位置に置く。デキュー（Dequeue）処理は、待ち行列の先頭にあるノード、つまり始点ノードからの最短距離を有するノードを待ち行列から除去する。]
[0064] タイブレイク・アルゴリズムは、現在の親及び新たな親の候補からそれぞれ開始して、分岐点までずっと、２個の等価経路を逆に辿ることにより、動作する。２個の分岐経路が異なるホップ数を有しうるという事実は、２個の経路は未知の等しくないホップ数により逆に辿られなければならないので、若干、事を複雑にする。この問題は、２個の経路のうちの長い方を常に最初に又は２個の経路が等価な場合には両方を同時に逆に辿ることにより、解決できる。或いは、この課題は、２個の経路が同一のホップ数を有する場合、及びその場合のみ、２個の経路が等価であると考えられることを保証することにより、完全に除去できる。これは、経路コストにホップ数を取り入れることにより、又はホップ数を１次のタイブレイカとして用いることにより、簡単に達成される。]
[0065] 以下の擬似コードは、２個の経路が同一のホップ数（従ってそれら経路の分岐するブランチも同一である）を有すると仮定したタイブレイク・アルゴリズムの実施を示す。]
[0066] タイブレイク関数は、２個の等しい経路の端にある２個のノードを取り込み、そのうちの１つを返して、該関数が２個の経路のうちのどちらを選択したかを示す。]
[0067] アルゴリズムが実行されるべき頻度は用途に依存する。ＰＬＳＢは、基本的に全ての対の最短経路（屡々、それらのサブセット）を計算する必要がある。この場合、ダイクストラのアルゴリズムは、ネットワーク内の全てのノード（正確には１つを除いて全部）に対して実行される必要がある。フロイドのアルゴリズムは、全ての対の最短経路を計算するので、１回だけ実行される必要がある。他の用途は、より少ない数の経路の計算しか要求しない（例えば、１つの最短経路のみが必要な場合は、ダイクストラのアルゴリズムは該経路の終端点の１つを始点として１回だけ実行されればよい）。]
[0068] 図８は、リンクにより相互接続されたノードＡ−Ｈ、Ｊのネットワークの例を示す。各リンクには、該リンクに関連付けられたメトリックが、該リンク上に整数値として示される。本ネットワークにはノードＡ及びＢの間に６個の異なる等価な最短経路が存在する。これらの最短経路は、その対応する長さ及び経路識別子と共に以下の表に示される。] 図８
[0069] これら６個の経路の全ては同一の長さ１０を有する。タイブレイク・アルゴリズムの非局所的バージョンは、最小経路識別子（ＡＢＣＦＨ）、つまり経路ＡＦＣＨＢを有する経路を選択する。この章の残りの部分は、タイブレイク・アルゴリズムの局所的バージョンが、等価経路として局所的なタイブレイク決定を行うことにより、どのように同一の結果に到達するか、及びダイクストラのアルゴリズムの実行中にサブ経路がどのように発見されるかを示す。]
[0070] ダイクストラのアルゴリズムは、ネットワーク内のノードの距離及び親（又は先行するノード）の表を初期化する。距離がゼロに設定される始点ノードを除いて、全ての距離は最初に無限大に設定される。この段階では親は不定である。]
[0071] ダイクストラのアルゴリズムは、優先待ち行列も初期化して、始点ノードＡのみを有するようにする。
TENT=[(A,O)]
ダイクストラ・ループの最初の反復で、ＴＥＮＴ内の最初の且つノードのみ、ノードＡを選択する。]
[0072] 次に、ノードＡの各近隣ノード、つまりノードＦ及びＧについて、それらの始点までの距離を更新し、ノードＡをそれらの親にする。最後に、これらの２個のノードはＴＥＮＴ優先待ち行列に追加される。]
[0073] このダイクストラのアルゴリズムの最初の反復中に、距離と親の表は次のようになる。]
[0074] この最初の反復の終了時に、優先待ち行列は次の通りである。
TENT=[(G,１),(F,２)]
ダイクストラ・ループの２回目の反復で、最小距離を有するノード、つまりノードＧが優先待ち行列から除去される。この反復で、未だ処理されていないＧの２個の近隣、つまりノードＣ及びＤが更新され、これらのノードは優先待ち行列に追加される。]
[0075] この２回目の反復の終了時に、優先待ち行列は次の通りである。
TENT=[(F,２),(D,４),(C,５)]
ダイクストラ・ループの３回目の反復では、ノードＦが優先待ち行列から除去される。この反復では、ノードＦの２個の近隣、つまりノードＣ及びＥが更新され、ノードＥが優先待ち行列に追加される（ノードＣは既に存在する）。ノードＣの距離は変化しないが、ノードＦを通過するノードＡ及びノードＣとの間の等価経路の新たな候補が存在する。]
[0076] 従って、タイブレイク・アルゴリズムは、ノードＦを通過するこの新たな経路とノードＧを通過する古い経路との間で選択するために呼び出されなければならい。これは図９に示される。タイブレイク・アルゴリズムは、ノードＣの親の新たな候補であるノードＦ、及びノードＣの古い親であるノードＧと共に呼び出される。ｏｌｄＭｉｎは古い親の識別子Ｇに設定され、ｎｅｗＭｉｎは新たな親の識別子Ｆに設定される。ノードＦ及びＧは同一の親（ノードＡ）を共有するので、タイブレイク・ループは実行されない。タイブレイクはｏｌｄＭｉｎとｎｅｗＭｉｎを単に比較し、ｎｅｗＭｉｎ＝Ｆ＜Ｇ＝ｏｌｄＭｉｎなので、ノードＦがノードＣの新たな親として選択される。] 図９
[0077] この３回目の反復の終了時に、優先待ち行列は次の通りである。
TENT=[(D,４),(E,４),(C,５)]
ダイクストラ・ループの４回目の反復で、距離４を有するノードうちの１つ、例えばノードＤが優先待ち行列から除去される。Ｄの２個の近隣うちの１個のみ、ノードＨは更新され、優先待ち行列に追加される。]
[0078] この４回目の反復の終了時に、優先待ち行列は次の通りである。
TENT=[(E,４),(C,５),(H,６)]
ダイクストラ・ループの５回目の反復では、ノードＥが優先待ち行列から除去される。Ｅの２個の近隣うちの１個のみ、ノードＪは更新され、優先待ち行列に追加される。]
[0079] この５回目の反復の終了時に、優先待ち行列は次の通りである。
TENT=[(C,５),(H,６),(J,６)]
ダイクストラ・ループの６回目の反復では、ノードＣが優先待ち行列から除去される。Ｃの２個の近隣、ノードＪ及びＨは、ノードＣを通過するノードＡまでの等価経路を有する。従って、タイブレイク・アルゴリズムは、ノードＪ及びＨのそれぞれに対して２回呼び出されなければならない。]
[0080] ノードＪでは、タイブレイク・アルゴリズムは、新たな可能性のある親であるノードＣ、及び古い親であるノードＥと共に呼び出される。ｏｌｄＭｉｎは古い親の識別子Ｅに設定され、ｎｅｗＭｉｎは新たな親の識別子Ｃに設定される。これら２個のノードＥ及びＣは同一の親（ノードＦ）を共有するので、タイブレイク・ループは実行されない。タイブレイクはｏｌｄＭｉｎとｎｅｗＭｉｎを単に比較し、ｎｅｗＭｉｎ＝Ｃ＜Ｅ＝ｏｌｄＭｉｎなので、新たな親が選択される。従って、ノードＪの親は、ノードＣにより置き換えられる。これは図１０に示される。] 図１０
[0081] ノードＨでは、タイブレイク・アルゴリズムは、新たな可能性のある親であるノードＣ、及び古い親であるノードＤと共に呼び出される。ｏｌｄＭｉｎは古い親の識別子Ｄに設定され、ｎｅｗＭｉｎは新たな親の識別子Ｃに設定される。これら２個のノードは異なる親を有するので、両経路は更に１ホップ引き返さなければならない。Ｄの親はＧであり、Ｇ＞ｏｌｄＭｉｎ（＝Ｄ）なので、ｏｌｄＭｉｎは変わらない。Ｃの親はＦであり、Ｆ＞ｎｅｗＭｉｎ（＝Ｃ）なので、ｎｅｗＭｉｎも変わらない。ノードＦ及びＧは同一の親、ノードＡを共有するので、引き返しループは停止する。次にタイブレイク・アルゴリズムはｏｌｄＭｉｎとｎｅｗＭｉｎを単に比較し、ｎｅｗＭｉｎ＝Ｃ＜Ｄ＝ｏｌｄＭｉｎなので、ノードＣがノードＨの新たな親になるよう選択される。これは図１１に示される。] 図１１
[0082] この６回目の反復の終了時に、優先待ち行列は次の通りである。
TENT=[(H,６),(J,６)]
ダイクストラ・ループの７回目の反復で、距離６を有するノードうちの１つ、例えばノードＨが優先待ち行列から除去される。Ｈの近隣うちの１個のみ、ノードＢは更新され、優先待ち行列に追加される。]
[0083] この７回目の反復の終了時に、優先待ち行列は次の通りである。
TENT=[(J,６),(B,１０)]
ダイクストラ・ループの８回目の反復では、ノードＪが優先待ち行列から除去される。Ｊの近隣のうちノードＢのみが更新される必要がある。ノードＢの距離は変化しないが、ノードＪを通過するノードＡ及びノードＣの間の等価経路の新たな候補が存在する。タイブレイク・アルゴリズムは、ノードＢの新たな可能性のある親であるノードＪ、及び古い親であるノードＨと共に呼び出される。ｏｌｄＭｉｎは古い親の識別子Ｈに設定され、ｎｅｗＭｉｎは新たな親の識別子Ｊに設定される。これら２個のノードＨ及びＪは同一の親（ノードＣ）を共有するので、タイブレイク・ループは実行されない。タイブレイクはｏｌｄＭｉｎとｎｅｗＭｉｎを単に比較し、ｏｌｄＭｉｎ＝Ｈ＜Ｊ＝ｎｅｗＭｉｎなので、古い親が選択され、ノードＢの親は同一のままである。]
[0084] この８回目の反復の終了時に、優先待ち行列は次の通りである。
TENT=[(B,１０)]
最後に、ダイクストラ・ループの最後の反復では、ノードＢが待ち行列から除去され、Ｂの如何なる近隣も更新できないので（ノードＢは始点ノードＡから最も遠いノードである）、アルゴリズムは終了する。]
[0085] ノードＡに到達するまでノードＢで開始し親に続くノードＡからノードＢへの最短経路の逆、ＢＨＣＦＡは、親のテーブルから直接読み出される。従って、局所的タイブレイク・アルゴリズムにより選択されたノードＡからノードＢへの最短経路は、逆経路ＡＦＣＨＢである。]
[0086] ノードＡ及びＢの間には６個の等価経路が存在するが、局所的タイブレイクは、ダイクストラのアルゴリズムの実行中に全部で４回だけ呼び出された。最初の反復で、タイブレイク・アルゴリズムは、サブ経路ＡＦＣ及びＡＧＣの間で選択しなければならなかった。タイブレイク・アルゴリズムは、サブ経路ＡＦＣを選択し、それにより２個の経路ＡＧＣＪＢ及びＡＧＣＨＢを更なる検討から除外した。２回目の反復で、タイブレイク・アルゴリズムは、サブ経路ＡＦＣＪ及びＡＦＥＪの間で選択しなければならなかった。タイブレイク・アルゴリズムは、サブ経路ＡＦＣＪを選択し、それにより第３の経路ＡＦＥＪＢを更なる検討から除外した。３回目の反復で、タイブレイク・アルゴリズムは、サブ経路ＡＧＤＨ及びＡＧＣＨの間で選択しなければならなかった。タイブレイク・アルゴリズムは、サブ経路ＡＧＣＨを選択し、それにより第４の経路ＡＧＤＨＢを更なる検討から除外した。最後に、４回目の反復で、タイブレイク・アルゴリズムは、経路ＡＦＣＨＢ及びＡＦＣＪＢの間で選択しなければならなかった。タイブレイク・アルゴリズムは、第５の経路ＡＦＣＪＢを除去し、経路ＡＦＣＨＢを最終的な解として選択した。]
[0087] 拡張をロードするための等価複数経路の選択
多くのネットワーク・アプリケーションでは、幾つかの等価経路を用いることは、一貫性のある方法で達成できるならば、屡々有利である。タイブレイク・アルゴリズムの２つの変形を用いることにより、ノードの対が存在する場合には該対の間の２個の等価経路を用いることが可能である。]
[0088] 図１２は、エッジ・ノードＸ及びＹがコア・ノードＡ、Ｂ、Ｃ、Ｄの完全なメッシュに二重に収容されている共通ネットワークの状況を示す。冗長性のため、各エッジ・ノードは、２個のコア・ノードに接続される。ノードＸはコア・ノードＡ及びＢに接続され、ノードＹはノードＣ及びＤに接続される。各コア・ノードは、全ての他のコア・ノードに接続される。例えば、ノードＡはＢ、Ｃ及びＤに接続される。このトポロジの有する問題は、１個の最短経路のみがノード対の間で用いられる場合に、通常の環境下では多くのアクセス能力が浪費されることである。複数の等価最短経路が２個のノード間に存在するとき、２個の経路を正確に一貫性をもって選択するために、タイブレイク・アルゴリズムの２つの変形を使用することができる。全てのノードにより合意された如何なる約束事も、等価経路間の選択を行うために用いることができる。１つの特に都合の良い約束事は、最小の識別子を有する第１の経路及び最大の識別子を有する第２の経路を選択することである。図１２では、コア・ノードは完全にメッシュ型なので、エッジ・ノードＸ及びＹの間に４個の等価経路(X,A,C,Y)、(X,A,D,Y)、(X,B,C,Y)、(X,B,D,Y)が存在する。タイブレイク・アルゴリズムの２つの変形は、これらの２個の経路を選択するだろう。
(X,min(A,B),min(C,D),Y)、及び
(X,min(A,B),min(C,D),Y)である。] 図１２
[0089] ノード識別子はユニークなので、min(A,B)!=max(A,B)andmin(C,D)!=max(C,D)である。これら２個の経路は最も多様性がある。これらの経路は、それらの終端点のみを共通に有する。図１２では、２個の選択された経路は、経路(X,A,C,Y)及び経路(X,B,D,Y)である。上述のタイブレイク方法の重要な特性の１つは、タイブレイクが決定する必要のある一式の経路のうちの１つに影響しないネットワークの変更が、タイブレイクの結果に如何なる影響も与えないことである。このような変更は、障害ノード又はリンクのような選択された経路上にないネットワークの部分を除去することを有してもよい。別の重要な特性は、複数の経路の等価経路が用いられるとき、１個の経路における障害が他の経路の安定性に影響を及ぼさないことである。同様に、リンクの追加は、複数の等価経路のうちの両方ではなく１個のみに影響を及ぼす。これは、ネットワークの安定性のために重要である。] 図１２
[0090] 図１３Ａ及び図１３Ｂは、本発明のタイブレイク方法の他の重要な特性を説明する。
−等価経路の存在下での単一の障害はループを実施できない。
−障害は、ループを閉じ、ルートの設定点をずらす。
−障害は、更に短い経路を生成できない。−タイブレイク・アルゴリズムは、等価経路の順位付けが最短経路を変更することを防止する。] 図１３Ａ 図１３Ｂ
[0091] 図１３Ａ及び図１３Ｂは、これらの特性を、ノードＡ、Ｂ、Ｃ、Ｄ及びＲを有する単純なネットワーク・トポロジで示す。図１３Ａを検討すると、Ｒと一式のノードＡ−Ｄとの間の最短経路はリンクＲ−Ａを用いる。ノードＡからノードＣに到達するには２個の等価経路の中から選択できる。上述のタイブレイク方法のうちの１つを用いて、ブランチＡ−Ｄ−Ｃではなく、ブランチＡ−Ｂ−Ｃが一貫して選択される。同様に、逆方向では、Ｃ−Ｄ−Ａの代わりにリンクＣ−Ｂ−Ａが一貫して選択される。図１３Ｂは、後の時点で、リンクＲ−Ａが障害したときの状況を示す。ノードＲは、次に最良のリンクＲ−Ｃを介して一式のノードＡ−Ｄに接続する。ノードＣからノードＡに到達するには２個の等価経路の中から選択できる。再び、Ｃ−Ｄ−Ａではなく、リンクＣ−Ｂ−Ａが一貫して選択される。この一貫性のあるタイブレイク・アルゴリズムを使用することなく、リンクＲ−Ａ内の障害に続いてループＡ−Ｂ−Ｃ−Ｄ−Ａが生じ得る。ノードＡ及びＢは遅くその動作が不規則であり、ノードＣ及びＤは機敏である。この特性は、マルチキャスト転送のループの自由を保障するのに特に有用である。] 図１３Ａ 図１３Ｂ
[0092] 本発明は、本願明細書に記載された実施形態に限定されない。これらの実施形態は、本発明の範囲から逸脱することなく変形及び変更が行われてよい。]

权利要求:

請求項1
パケット転送ネットワークの第１のノードでパケットを転送するのに用いられる転送情報を決定する方法であって、該ネットワークの各ノードはユニークなノード識別子を有し、当該方法は：前記第１のノードと前記ネットワークの第２のノードとの間の最短経路を決定する段階；複数の最短経路が実質的に等価であるときを決定する段階；実質的な等価経路毎に、該経路内にあるノードのセットを定めるノード識別子のセットを形成する段階；第１の順序付け基準はノード識別子が前記経路内に現れる順序とは独立であり、該第１の順序付け基準を用いてノード識別子の各セットを順序付け、経路識別子を形成する段階；前記経路識別子を比較することにより、複数の等価経路の間で選択する段階；を有する方法。
請求項2
前記複数の最短経路が実質的に等価であるときを決定する段階は、複数の最短経路が正確に等価であるときを決定する段階で置き換えられる、ことを特徴とする請求項１に記載の方法。
請求項3
前記第１の順序付け基準は、完全に順序付けられたノード識別子のセットを生成する、ことを特徴とする請求項１に記載の方法。
請求項4
前記第１の順序付け基準は、昇順の辞書式順序、降順の辞書式順序のうちの１つである、ことを特徴とする請求項１に記載の方法。
請求項5
第２の順序付け基準を用いて、複数の経路識別子を順序付きリストに順序付ける段階；を更に有する請求項１に記載の方法。
請求項6
前記第２の順序付け基準は、完全に順序付けられた経路識別子のセットを生成し、前記複数の等価経路の間で選択する段階は、経路識別子の順序付きリストの一端に現れる等価経路を選択する段階を有する、ことを特徴とする請求項５に記載の方法。
請求項7
前記複数の等価経路の間で選択する段階は、経路識別子の順序付きリストの最初、経路識別子の順序付きリストの最後のうちの１つに現れる等価経路を選択する段階を有する、ことを特徴とする請求項６に記載の方法。
請求項8
前記第２の順序付け基準は、昇順の辞書式順序、降順の辞書式順序のうちの１つである、ことを特徴とする請求項５に記載の方法。
請求項9
異なる第１の順序付け基準及び共通の第２の順序付け基準を用いること、共通の第１の順序付け基準及び異なる第２の順序付け基準を用いること、の少なくとも１つにより前記実質的な等価経路のうちの２つを選択する段階；を更に有する請求項５に記載の方法。
請求項10
２つの異なる第１の順序付け基準及び共通の第２の順序付け基準を用いること、同一の２つの第１の順序付け基準及び異なる第２の順序付け基準を用いること、により前記実質的な等価経路のうちの４つを選択する段階；を更に有する請求項５に記載の方法。
請求項11
前記第１の順序付け基準は、昇順の辞書式順序、降順の辞書式順序であり；前記第２の順序付け基準は、昇順の辞書式順序、降順の辞書式順序である；ことを特徴とする請求項９に記載の方法。
請求項12
パケット転送ネットワークの第１のノードでパケットを転送するのに用いられる転送情報を決定する方法であって、該ネットワークの各ノードはユニークなノード識別子を有し、当該方法は：最短経路ツリーを繰り返し形成することにより、前記第１のノードと前記ネットワークの第２のノードとの間の最短経路を決定する段階；各等価経路は該等価経路に共通の分岐ノードから分岐するブランチを有し、前記最短経路ツリーを形成する間、複数の経路が等価であるときを決定する段階；各分岐するブランチで、第１の順序付け基準を用いてノード識別子を識別し、ブランチ識別子を形成する段階；前記ブランチ識別子を比較することにより、複数のブランチの間で選択する段階；を有する方法。
請求項13
前記第１の順序付け基準は、全体の選択基準を用い、各ブランチのノード識別子を比較し選択する、ことを特徴とする請求項１２記載の方法。
請求項14
前記第１の選択基準は、辞書式順序を用い、各ブランチのノード識別子を比較し選択する、ことを特徴とする請求項１２記載の方法。
請求項15
前記第１の選択基準は、辞書式順序を用い、辞書式順序の最初に現れるノード識別子、辞書式順序の最後に現れるノード識別子、のうちの１つを選択する、ことを特徴とする請求項１４記載の方法。
請求項16
前記分岐ノードへ引き返す間に、前記各分岐ブランチ内の第１の選択基準を満たすノード識別子を記録する段階；を更に有する請求項１２に記載の方法。
請求項17
各逆行段階で、前記記録されたノード識別子を、該段階で遭遇した新たなノード識別子と比較し、前記第１の選択基準を満たすノード識別子を記録する段階；を更に有する請求項１６に記載の方法。
請求項18
第２の選択基準を用いてブランチ識別子を選択することにより、複数のブランチの間で選択する段階；を更に有する請求項１２に記載の方法。
請求項19
前記第２の選択基準は、全体の順序付け基準を用い、ブランチ識別子を比較し選択する、ことを特徴とする請求項１８記載の方法。
請求項20
前記第２の選択基準は、辞書式順序を用い、ブランチ識別子を比較し選択する、ことを特徴とする請求項１９記載の方法。
請求項21
前記第２の選択基準は、辞書式順序を用い、辞書式順序の最初に現れるノード識別子、辞書式順序の最後に現れるノード識別子、のうちの１つを選択する、ことを特徴とする請求項２０記載の方法。
請求項22
対に基づき、前記複数のブランチの間で選択する、ことを特徴とする請求項１２に記載の方法。
請求項23
異なる第１の選択基準及び共通の第２の選択基準を用いること、共通の第１の選択基準及び異なる第２の選択基準を用いること、の少なくとも１つにより前記等価経路のうちの２つを選択する段階；を更に有する請求項１８に記載の方法。
請求項24
２つの異なる第１の選択基準及び共通の第２の選択基準を用いること、同一の２つの第１の選択基準及び異なる第２の選択基準を用いること、により前記等価経路のうちの４つを選択する段階；を更に有する請求項１８に記載の方法。
請求項25
前記第１の選択基準は、最大ノード識別子、最小ノード識別子であり；前記第２の選択基準は、最大ブランチ識別子、最小ブランチ識別子である；ことを特徴とする請求項２３に記載の方法。
請求項26
ダイクストラのアルゴリズムを用いて最短経路ツリーを反復的に形成する段階；を有する請求項１２に記載の方法。
請求項27
プロセッサにより実行されると該プロセッサに請求項１に記載の方法を実施させる命令を有する機械可読媒体を有するコンピュータ・プログラム。
請求項28
請求項１の方法を実行するようにされるプロセッサを有するネットワーク・ノード。
請求項29
それぞれ請求項１に記載の方法を一貫して適用し等価経路の間で選択するノードのネットワーク。
請求項30
プロセッサにより実行されると該プロセッサに請求項１２に記載の方法を実施させる命令を有する機械可読媒体を有するコンピュータ・プログラム。
請求項31
請求項１２の方法を実行するようにされるプロセッサを有するネットワーク・ノード。
請求項32
それぞれ請求項１２に記載の方法を一貫して適用し等価経路の間で選択するノードのネットワーク。